﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/single-element-in-a-sorted-array/
/*
题目描述：
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

 

示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:
输入: nums =  [3,3,7,7,10,11,11]
输出: 10
 

提示:
1 <= nums.length <= 105
0 <= nums[i] <= 105
*/

// 开始解题：
// 方法1——位运算
int singleNonDuplicate(int* nums, int numsSize) {
    int i = 0;
    int answer = 0;
    for (i = 0; i < numsSize; i++) {
        answer ^= nums[i];
    }
    return answer;
}
//时间复杂度：O(n)，n为数组的长度。
// 空间复杂度：O(1)，我们只需要用到常数的额外空间。